/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <queue> 
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */



/**
 * DFS 深度优先--递归
 * 状态、子问题：当前坐标(i, j)看成状态
 * 递归搜索(i-1, j), (i+1, j), (i, j-1), (i, j+1)
 * 记录是否访问过的全局状态
 */
class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int ans = dfs(0,0,m,n,k,visited);
        return ans;
    }
    // 实现位数和
    int digit_sum(int a){
        int sum = 0;
        while(a){
            sum += a%10;
            a=a/10;
        }
        return sum;
    }
    /** 深度优先
     * (i, j)表示状态
     * (m, n)表示边界
     * k用于检测
     */
    int dfs(int i, int j, int m, int n, int k, vector<vector<bool>> &visited){
        if(i<0 || j<0 ||i>=m || j>=n || digit_sum(i) + digit_sum(j) > k || visited[i][j] == true){
             return 0;
         }
         visited[i][j] = true;
         return 1 + dfs(i + 1, j, m, n, k, visited) + dfs(i - 1, j, m, n, k, visited)
                + dfs(i, j + 1, m, n, k, visited) + dfs(i, j - 1, m, n, k, visited);
    }
};


int main(int argc, const char** argv) {
    Solution solu = Solution();
    cout << solu.movingCount(3,2,1) << endl;
    // cout << solu.movingCount(0,0,1) << endl;

    return 0;
}